<?php

namespace App\Http\Controllers\v1\algorithmAndDataStruct;

use App\Http\Controllers\Controller;

/*
 * 链表本身，包含一个指向链表头部节点和链表的操作增加，删除，遍历链表，是否是空链表
 */
class LinkedList extends Controller
{
    public $head;

    public function __construct()
    {
        $this->head = null;
    }

    public function isEmpty(): bool
    {
        return $this->head === null;
    }

    /**
     * 增加数据节点
     * @timeComplexity n
     * @param $data
     * @return void
     */
    public function insert($data)
    {
        //初始化节点
        $newNode = new Node($data);
        //链表头部节点是null把$newNode赋值给当前节点
        if ($this->isEmpty()) {
            $this->head = $newNode;
        } else {
            //把$newNode加入节点尾部
            $currentNode = $this->head;
            while ($currentNode->next !== null) {
                $currentNode = $currentNode->next;
            }
            $currentNode->next = $newNode;
        }
    }

    public function delete($data)
    {
        if ($this->isEmpty()) {
            return false;
        }
        //当前节点的数据和要删除的数据相等，移除当前节点
        if ($this->head->data === $data) {
            $this->head = $this->head->next;
            return true;
        }
        //不相等则找下一个节点，判断是否等于要删除的数据，以此类推
        //注意终止条件：当前节点不能为空和当前节点是下个节点，上个节点是当前节点
        $previousNode = $this->head;
        $currentNode  = $this->head->next;
        while ($currentNode !== null) {
            if ($currentNode->data === $data) {
                $previousNode->next = $currentNode->next;
                return true;
            }
            $previousNode = $currentNode;
            $currentNode  = $currentNode->next;
        }
        return false;
    }

    /**
     * 遍历链表
     * @return void
     */
    public function display(): void
    {
        $currentNode = $this->head;
        while ($currentNode !== null) {
            dump($currentNode->data);
            $currentNode = $currentNode->next;
        }
    }


    /**
     * 翻转单向链表
     * @return Node
     */
    public function reversal(): Node
    {
       $previousNode = null;
       $currentNode = $this->head;
       while ($currentNode !== null) {
           $nextNode = $currentNode->next;
           $currentNode->next = $previousNode;
           $previousNode = $currentNode;
           $currentNode = $nextNode;
       }
       return $previousNode;
    }

    /**
     * 判断链表是否有环
     * @param $currentNode
     * @return bool
     */
    public function isRoll($currentNode): bool
    {

        if (!($currentNode && $currentNode->next)) {
            return false;
        }
        $slow = $currentNode;
        $fast = $currentNode->next;
        while ($slow != $fast) {
            if (!($slow && $fast)) {
                return false;
            }
            $slow = $slow->next;
            $fast = $fast->next->next;
        }
        return true;
    }
}